//检验一棵二叉树是否搜索二叉树（左孩子小于（不能等于）根节点），（右孩子大于根节点）
//递归法
//思路1：对搜索二叉树进行中序遍历后的数组是严格递增的，可以先遍历得到数组再检验
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
};
#include <vector>
using std::vector;
vector<int>& traversal(TreeNode* cur,vector<int>& res){
    if(!cur) return res;
    traversal(cur->left,res);
    res.push_back(cur->val);
    traversal(cur->right,res);
    return res;
}
bool isValidBST_(TreeNode* root) {
    if(!root) return false;
    vector<int>array;
    traversal(root,array);
        bool chk=true;
    for(int i=0;i<array.size()-1;i++){
        if(array[i]>=array[i+1]) chk=false;
    }
    return chk;
}





//也可以直接判断
TreeNode* pre;
bool isValidBST(TreeNode* root) {
    if(!root) return true;
    bool left=isValidBST(root->left);

    if(pre&&pre->val>=root->val) return false;
    pre=root;   //记录前一个节点，用来比较

    bool right=isValidBST(root->right);
    return left&&right;
}
//pre节点就是中序遍历中当前节点的上一个遍历节点
//则pre节点的值总是小于当前节点的值


#include <stack>
using std::stack;
//迭代法
bool _isValidBST(TreeNode* root){
    if(!root) return true;
    stack<TreeNode*> st;
    TreeNode* pre=nullptr;
    TreeNode* cur=root;
    while (cur||!st.empty())
    {
        if(cur){
            st.push(cur);
            cur=cur->left;      //左
        }
        else{
            cur=st.top();   st.pop();
            if(pre&&pre->val>=cur->val) return false; 
            pre=cur;    //记录前一个节点，然后遍历下一个节点
            
            cur=cur->right;// 右
        }
    }
    return true;
    
}